#include "IMemPool.h"
#include "stdlib.h"
#include "stdio.h"

CMemHeadList::CMemHeadList()
{
    m_len = 0;
    m_pHead = NULL;
    m_pTail = NULL;
}

void CMemHeadList::clear()
{
    m_len = 0;
    m_pHead = NULL;
    m_pTail = NULL;
}


int CMemHeadList::addNode(TMemBlockHead* pNode)
{
    if(m_len == 0)
    {
        m_pHead = pNode;
        m_pTail = pNode;

        pNode->m_pPreNode = NULL;
        pNode->m_pNextNode = NULL;
    }
    else
    {
        m_pTail->m_pNextNode = pNode;
        pNode->m_pPreNode = m_pTail;
        pNode->m_pNextNode = NULL;

        m_pTail = pNode;
    }
    m_len++;
    return m_len;
}

/*
int CMemHeadList::delNode(TMemBlockHead* pNode) 
{
    TMemBlockHead* pDelNode = findNode(pNode);
    if(pDelNode == NULL) return m_len;
    if(pDelNode->m_pPreNode != NULL)
    {
        pDelNode->m_pPreNode->m_pNextNode = pDelNode->m_pNextNode;
    }
    else
    {
        m_pHead = pDelNode->m_pNextNode;
    }
    if(pDelNode->m_pNextNode != NULL)
    {
        pDelNode->m_pNextNode->m_pPreNode = pDelNode->m_pPreNode;
    } 
    else
    {
        m_pTail = pDelNode->m_pPreNode;
    }
    delete pDelNode;
    m_len--;
    return m_len;
}
*/

int CMemHeadList::removeNode(TMemBlockHead* pNode)
{
    TMemBlockHead* pDelNode = findNode(pNode);
    if(pDelNode == NULL) return m_len;
    if(pDelNode->m_pPreNode != NULL)
    {
        pDelNode->m_pPreNode->m_pNextNode = pDelNode->m_pNextNode;
    }
    else
    {
        m_pHead = pDelNode->m_pNextNode;
    }
    if(pDelNode->m_pNextNode != NULL)
    {
        pDelNode->m_pNextNode->m_pPreNode = pDelNode->m_pPreNode;
    } 
    else
    {
        m_pTail = pDelNode->m_pPreNode;
    }
    pDelNode->m_pPreNode = NULL;
    pDelNode->m_pNextNode = NULL;
    m_len--;
    return m_len;
}

TMemBlockHead* CMemHeadList::findNode(TMemBlockHead* pNode)
{
    if(m_len == 0) return NULL;
    for(TMemBlockHead* pCurNode = m_pHead;pCurNode!=NULL;pCurNode=pCurNode->m_pNextNode)
    {
        if(pCurNode->m_pData == pNode->m_pData)
        {
            return pCurNode;
        }
    }
    return NULL;
}

TMemBlockHead* CMemHeadList::findBestNode(int len)
{
    if(m_len == 0) return NULL;
    int leftLen = m_pHead->m_len;
    TMemBlockHead* pBestNode = NULL;
    for(TMemBlockHead* pCurNode = m_pHead;pCurNode!=NULL;pCurNode=pCurNode->m_pNextNode)
    {
        if((pCurNode->m_len - len) >= 0
            && leftLen > (pCurNode->m_len - len))
        {
            pBestNode = pCurNode;
        }
    }
    return pBestNode;
}


void CMemHeadList::dump()
{
    printf("== begin MemHead list ==\n");
    int i = 1;
    for(TMemBlockHead* pCurNode = m_pHead;pCurNode!=NULL;pCurNode=pCurNode->m_pNextNode)
    {
        printf("%d/%d: ",i++,m_len);
        printf("preNodeAddr=%p,curNodeAddr=%p,nextNodeAddr=%p,pDataAddr=%p,DataLen=%d,memHeadLen=%d,memBlkLen=%d\n"
            ,pCurNode->m_pPreNode,pCurNode,pCurNode->m_pNextNode
            ,pCurNode->m_pData,pCurNode->m_len,sizeof(TMemBlockHead)
            ,pCurNode->m_len+sizeof(TMemBlockHead));
    }
    printf("== end MemHead list ==\n\n");
}


void CMemHeadList::operator= (CMemHeadList& node)
{
    this->m_len = node.m_len;
    this->m_pHead = node.m_pHead;
    this->m_pTail = node.m_pTail;
}

void CMemHeadList::sortInc()
{
    CMemHeadList incList;
    TMemBlockHead* pMinNode = NULL;
    do
    {
        pMinNode = findMinNode();
        if(pMinNode != NULL)
        {
            removeNode(pMinNode);
            incList.addNode(pMinNode);
        }
    }while(pMinNode != NULL);
    *this = incList;
}

void CMemHeadList::sortDec()
{
    CMemHeadList decList;
    TMemBlockHead* pMaxNode = NULL;
    do
    {
        pMaxNode = findMaxNode();
        if(pMaxNode != NULL)
        {
            removeNode(pMaxNode);
            decList.addNode(pMaxNode);
        }
    }while(pMaxNode != NULL);
    *this = decList;
}



TMemBlockHead* CMemHeadList::findMinNode()
{
    TMemBlockHead* pMinNode = m_pHead;
    for(TMemBlockHead* pCurNode = m_pHead;pCurNode!=NULL;pCurNode=pCurNode->m_pNextNode)
    {
        if(pMinNode->m_pData > pCurNode->m_pData)
        {
            pMinNode = pCurNode;
        }
    }
    return pMinNode;
}

TMemBlockHead* CMemHeadList::findMaxNode()
{
    TMemBlockHead* pMaxNode = m_pHead;
    for(TMemBlockHead* pCurNode = m_pHead;pCurNode!=NULL;pCurNode=pCurNode->m_pNextNode)
    {
        if(pMaxNode->m_pData < pCurNode->m_pData)
        {
            pMaxNode = pCurNode;
        }
    }
    return pMaxNode;
}

CBigMemMgr::CBigMemMgr()
{
    m_freeList.clear();
    m_useList.clear();
}

CBigMemMgr::~CBigMemMgr()
{

}

int CBigMemMgr::init(char* pBuff,int len)
{
    //not ength for head
    if(len < sizeof(TMemBlockHead)) return -1;
    //create head in buff
    TMemBlockHead* pBlkHead = (TMemBlockHead*)pBuff;
    pBlkHead->m_pNextNode = NULL;
    pBlkHead->m_pData = ((char*)pBlkHead) + sizeof(TMemBlockHead);
    pBlkHead->m_len = len - sizeof(TMemBlockHead);
    //get the address of Mem Head
    m_freeList.addNode(pBlkHead);
    return 0;
}

char* CBigMemMgr::malloc(int len)
{
    TMemBlockHead* pMallocHead = m_freeList.findBestNode(len);
    if(pMallocHead == NULL) return NULL;
    m_freeList.removeNode(pMallocHead);

    if((pMallocHead->m_len - len) > sizeof(TMemBlockHead))// ength for a free block
    {
        TMemBlockHead* pNewFreeHead = (TMemBlockHead*)(pMallocHead->m_pData+len);
        pNewFreeHead->m_pData = (char*)pNewFreeHead + sizeof(TMemBlockHead);
        pNewFreeHead->m_len = pMallocHead->m_len - len - sizeof(TMemBlockHead);

        m_freeList.addNode(pNewFreeHead);
    }
    pMallocHead->m_len = len;
    m_useList.addNode(pMallocHead);

    m_freeList.sortInc();
    mergeFree(m_freeList);
    return pMallocHead->m_pData;
}

int CBigMemMgr::free(char* pBuff)
{
    TMemBlockHead blkFinder;
    blkFinder.m_pData = pBuff;

    TMemBlockHead* pToFreeNode = m_useList.findNode(&blkFinder);
    if(pToFreeNode == NULL) return -1;
    
    m_useList.removeNode(pToFreeNode);

    m_freeList.addNode(pToFreeNode);
    m_freeList.sortInc();
    mergeFree(m_freeList);
    return 0;
}

void CBigMemMgr::dump()
{
    printf("============================\n");
    printf("free list\n");
    m_freeList.dump();
    printf("use list\n");
    m_useList.dump();
    printf("============================\n\n");
}

void CBigMemMgr::mergeFree(CMemHeadList& list)
{
    if(list.m_len == 1 || list.m_len == 0) return;
    TMemBlockHead* pPreNode = list.m_pHead;
    TMemBlockHead* pNode = list.m_pHead->m_pNextNode;
    while(pNode != NULL)
    {
        if((pPreNode->m_pData + pPreNode->m_len) == (char*)pNode)
        {
            list.removeNode(pNode);
            pPreNode->m_len = pPreNode->m_len + sizeof(TMemBlockHead) + pNode->m_len;
            pNode = pPreNode->m_pNextNode;
        }
        else
        {
            pPreNode = pPreNode->m_pNextNode;
            pNode = pNode->m_pNextNode;
        }
    }
}

